Unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
In computer networks such as the Internet, packets of data are sent from a source to a destination via a network of elements including links (communication paths such as telephone or optical lines) and nodes (for example, routers directing the packets along one or more of a plurality of links connected to it) according to one of various routing protocols.
One class of routing protocol is the link state protocol. The link state protocol relies on a routing algorithm resident at each node. Each node on the network advertises, throughout the network, links to neighboring nodes and provides a cost associated with each link, which can be based on any appropriate metric such as link bandwidth or delay and is typically expressed as an integer value. A link may have an asymmetric cost, that is, the cost in the direction AB along a link may be different from the cost in a direction BA. Based on the advertised information in the form of a link state packet each node constructs a link state database (LSDB), which is a map of the entire network topology, and from that constructs generally a single optimum route to each available node based on an appropriate algorithm such as, for example, a shortest path first (SPF) algorithm. As a result a “shortest path spanning tree” (SPT) is constructed, rooted at the node and showing an optimum path including intermediate nodes to each available destination node. The results of the SPF are stored in a routing information base (RIB) and based on these results the forwarding information base (FIB) or forwarding table is updated to control forwarding of packets appropriately. When there is a network change a link state packet representing the change is flooded through the network by each node adjacent the change, each node receiving the link state packet sending it to each adjacent node.
As a result, when a data packet for a destination node arrives at a node, the receiving node identifies the optimum route to that destination and forwards the packet to the next node along that route. The next node repeats this step and so forth.
In normal forwarding each node decides, irrespective of the node from which it received a packet, the next node to which the packet should be forwarded. In some instances this can give rise to a “loop,” in which the forwarding decisions of a group of nodes result in endlessly forwarding packets in a loop among the nodes, without reaching the destination. In particular, loops can occur when the databases (and corresponding forwarding information) are temporarily de-synchronized during a routing transition. For example, because of a change in the network, a new LSP may be propagated that induces creating a loop in the RIB or FIB. As a specific example, if node A sends a packet to node Z via node B, comprising the optimum route according to its SPF, node B, according to its SPF could determine that the best route to node Z is via node A and node B then could send the packet back. Looped forwarding can continue for as long as the loop remains represented in the RIB or FIB, although usually the packet will have a maximum hop count after which it is discarded. Such a loop can be a direct loop between two nodes or an indirect loop around a circuit of nodes.